package com.shm.leetcode;

/**
 * 123. 买卖股票的最佳时机 III
 * 给定一个数组，它的第 i 个元素是一支给定的股票在第 i 天的价格。
 *
 * 设计一个算法来计算你所能获取的最大利润。你最多可以完成 两笔 交易。
 *
 * 注意: 你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。
 *
 * 示例 1:
 *
 * 输入: [3,3,5,0,0,3,1,4]
 * 输出: 6
 * 解释: 在第 4 天（股票价格 = 0）的时候买入，在第 6 天（股票价格 = 3）的时候卖出，这笔交易所能获得利润 = 3-0 = 3 。
 *      随后，在第 7 天（股票价格 = 1）的时候买入，在第 8 天 （股票价格 = 4）的时候卖出，这笔交易所能获得利润 = 4-1 = 3 。
 * 示例 2:
 *
 * 输入: [1,2,3,4,5]
 * 输出: 4
 * 解释: 在第 1 天（股票价格 = 1）的时候买入，在第 5 天 （股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5-1 = 4 。
 *      注意你不能在第 1 天和第 2 天接连购买股票，之后再将它们卖出。
 *      因为这样属于同时参与了多笔交易，你必须在再次购买前出售掉之前的股票。
 * 示例 3:
 *
 * 输入: [7,6,4,3,1]
 * 输出: 0
 * 解释: 在这个情况下, 没有交易完成, 所以最大利润为 0。
 * @author SHM
 */
public class MaxProfitV {

    public int maxProfit(int[] prices) {
        if (prices==null||prices.length==0){
            return 0;
        }
        return dfs(prices,0,0,0);
    }

    /**
     * 递归
     * 之前的股票系列题目可以无限次数的买卖、或者只能买卖一次，很显然买卖两次的状态转换就比之前要复杂多了，这也就是本题的难点所在。
     * 需要注意的是，我们最终求出的最大利润，不一定非得交易两次，也可能一次都不交易(行情不好不炒股了)，或者只交易了一次(如示例2)。
     *
     * 我们先看一下，买卖两次时是怎么进行状态转换的
     *
     *
     * 一开始处于初始状态，也就是什么都不做，不买也不卖
     * 初始状态只能转向买入1状态(第一次买入股票)，也就是买入一股；当买入一股后，我们有两种选择:
     *
     * 可以立马转向卖出1状态(第一次卖出股票)
     * 或者转入保持不动状态，相当于手里一直有这一股，等待一个好时机之后再卖出。
     * 在卖出1状态时:
     *
     * 我们可以立马转入买入2状态(第二次买入股票)
     * 或者转入保持不动状态，相当于此时手里没有股票了，等待一个好时机后再买入。
     * 买入2和卖出2也是类似的
     * 卖出2执行完后，就只能转入到交易结束状态了，后面就无法再买卖了。
     *
     * 通过上面的这个状态转换图，我们可以用三个变量来表示买卖两次的交易状态
     *
     * index，用来表示当前是哪一天
     * status，用来表示当前状态是买入、还是卖出
     * k，用来表示交易了几次
     * 如果状态是是买入:
     *
     * 那么可以保持不动
     * 或者马上卖掉
     * 如果状态是卖出:
     *
     * 可以保持不动(等待更好的股价出现，暂时不买)
     * 或者立马再买一股
     * 同时将count数+1，表示交易过一次了
     * 对于数组[1,2,3,4,5]其递归调用树如下:
     *
     *
     * 第一次只能买入，对应上图也就是节点1的买1，当然也可以选择不买，也就是不动。
     * 第一次买之后可以立刻卖掉，也就是上图中 根 --买1--> 1 --卖1--> 2这条路线。这就对应了第一张图中买入1转换到卖出1的过程。
     * 或者也可以选择不动，对应到上图就是根 --买1--> 1 --不动--> 2这条路线。对应第一张图中买1后转入到保持不动这个过程。
     *
     * 卖1 到 买2、以及买2 到卖2 这之间的转换关系也是类似的，这里的调用链太长了我就没画了，大家可以看下图一和图二，对比一下这个关系。
     * 第二次卖出后就无法再交易了，所以从调用树上来看，后面就不会再有调用的子节点了。
     *
     * 作者：wang_ni_ma
     * 链接：https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-iii/solution/wu-chong-shi-xian-xiang-xi-tu-jie-123mai-mai-gu-pi/
     * @param prices
     * @param index
     * @param status
     * @param k
     * @return
     */

    //超时
    public int dfs(int[] prices,int index,int status,int k){
        //递归终止条件，数组执行到头了，或者交易了两次了
        if (index==prices.length||k==2){
            return 0;
        }
        //定义三个变量，分别记录[不动]、[买]、[卖]
        int a=0,b=0,c=0;
        //保持不动
//        a=dfs(prices,index+1,0,k); //易错点status
        a=dfs(prices,index+1,status,k);
        if (status==1){
            //递归处理卖的情况，这里需要将k+1，表示执行了一次交易
            b = dfs(prices,index+1,0,k+1)+prices[index];
        }else {
            //递归处理买的情况
            c = dfs(prices, index + 1, 1, k)-prices[index];
        }
        //最终结果就是三个变量中的最大值
        return Math.max(Math.max(a,b),c);
    }

    /**
     * 动态规划 三维数组
     * 在递归实现时，我们用了三个变量：index、status、k。这里我们定义一个三维数组
     * dp[n][3][2] 这里的n表示天数
     *
     * dp[i][0][0]：表示第i天交易了0次时卖出后的累计最大利润
     * dp[i][0][1]：表示第i天交易了0次时买入后的累计最大利润
     * dp[i][1][0]：表示第i天交易了1次时卖出后的累计最大利润
     * dp[i][1][1]：表示第i天交易了1次时买入后的累计最大利润
     * dp[i][2][0]：表示第i天交易了2次时卖出后的累计最大利润
     * dp[i][2][1]：表示第i天交易了2次时买入后的累计最大利润
     * 注意，最后一个dp[i][2][1] 实际是不存在的，因为交易两次后，就不能再买入了。
     *
     * 我们来分析一下上面定义的dp数组：
     *
     *
     * dp[i][0][0]：对应于初始状态，第i天0次交易卖出，既然都没交易，那何来卖出呢，所以只能是0。
     * dp[i][0][1]和dp[i][1][0] 这两个是一对，对应到上图中就是第一次买入、第一次卖出。
     * dp[i][1][1]和dp[i][2][0] 这两个也是一对，对应到上图中就是第二次买入、第二次卖出。
     * 从这里我们也能看出为什么dp[i][2][1]是无效的。
     *
     * 再看一下状态转换公式如何推导的
     * 前面我们分析过了，买入1这个状态只能从两个地方转换来，买入1本身(保持不动)，或者是初始状态转换而来。
     * 而卖出1这个状态，也只能从两个地方转换而来，卖出1本身(保持不动)，或者从买入1转来。
     *
     *
     * 那么根据上面描述，我们可以算出第一次买卖的DP公式：
     *
     *
     * 第一次买入：从初始状态转换而来，或者第一次买入后保持不动
     * dp[i][0][1] = max(dp[i-1][0][1],dp[i-1][0][0]-prices[i])
     *
     * 第一次卖出：从第一次买入转换而来，或者第一次卖出后保持不动
     * dp[i][1][0] = max(dp[i-1][1][0],dp[i-1][0][1]+prices[i])
     * 再来分下一下第二次的买卖过程：
     * 同样，第二次买入只能从 第一次买入转换来，或者保持不动
     * 第二次卖出只能从第二次买入转换来，或者保持不动
     *
     *
     * 那么根据上面描述，我们可以算出第二次买卖的DP公式：
     *
     *
     * 第二次买入：从第一次卖出转换而来，或者第二次买入后保持不动
     * dp[i][1][1] = max(dp[i-1][1][1],dp[i-1][1][0]-prices[i])
     *
     *
     * 第二次卖出：从第二次买入转换而来，或者第二次卖出后保持不动
     * dp[i][2][0] = max(dp[i-1][2][0],dp[i-1][1][1]+prices[i])
     * 我们把第一次买卖、第二次买卖的DP公式合到一起，就拿到了完整的推导过程。
     * 之后我们还需要处理一下 第一天的初始化状态(具体请看代码部分)
     * 最后求的利润最大值就保存在 dp[n-1][0][0]、dp[n-1][0][1]、dp[n-1][1][0]、dp[n-1][1][1]、dp[n-1][2][0]中，我们求出这几个值的max再返回就可以了。
     *
     * 作者：wang_ni_ma
     * 链接：https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-iii/solution/wu-chong-shi-xian-xiang-xi-tu-jie-123mai-mai-gu-pi/
     * @param prices
     * @return
     */
    public int maxProfit_2(int[] prices) {
        if (prices == null || prices.length == 0) {
            return 0;
        }
        int n = prices.length;
        //定义三维数组，第i天、交易了多少次、当前的买卖状态
        int[][][] dp = new int[n][3][2];
        //初始化第一天，这里的dp[0][2][1]可以不用管，后面也不会用到
        dp[0][0][0]=0;
        dp[0][0][1]=-prices[0];
        dp[0][1][0]=0;
        dp[0][1][1]=-prices[0];
        dp[0][2][0]=0;
        for (int i = 1; i < n; i++) {
            //dp[i][0][0]相当于初始状态，它只能从初始状态转换来
            dp[i][0][0]=dp[i-1][0][0];
            //处理第一次买入、第一次卖出
            dp[i][0][1]=Math.max(dp[i-1][0][1],dp[i-1][0][0]-prices[i]);
            dp[i][1][0]=Math.max(dp[i-1][1][0],dp[i-1][0][1]+prices[i]);
            //处理第二次买入、第二次卖出
            dp[i][1][1]=Math.max(dp[i-1][1][0]-prices[i],dp[i-1][1][1]);
            dp[i][2][0]=Math.max(dp[i-1][1][1]+prices[i],dp[i-1][2][0]);
        }
        //返回最大值
        int max0 = Math.max(dp[n - 1][0][0], dp[n - 1][0][1]);
        int max1 = Math.max(dp[n - 1][1][0], dp[n - 1][1][1]);
        return Math.max(Math.max(max0,max1),dp[n-1][2][0]);
    }

    /**
     * 动态规划 二维数组
     * 这里参考了 liweiwei1419 大佬的题解
     * 原文地址 -> 这里
     *
     * 这我们定义一个二维数组 dp[n][5]
     * 这的n表示天数，5表示5种不同的状态
     *
     * 其实这个转换跟 三维数组的有点类似，在三维数组中我们定义了交易次数、买卖状态。 因为交易次数和买卖状态都是常数个，所以我们把这两者整合到一起了。
     *
     *
     * 我们定义了5种状态来代替三维数组中的交易次数和买卖状态，物种状态分别如上图
     *
     * dp[i][0] 初始化状态
     * dp[i][1] 第一次买入
     * dp[i][2] 第一次卖出
     * dp[i][3] 第二次买入
     * dp[i][4] 第二次卖出
     * 根据上面的转换关系，我们来推到一下DP公式
     * 首先是第一次买卖：
     *
     *
     * 第一次买入：从初始状态转换而来，或者第一次买入后保持不动
     * dp[i][1] = max(dp[i-1][1],dp[i-1][0]-prices[i])
     *
     * 第一次卖出：从第一次买入转换而来，或者第一次卖出后保持不动
     * dp[i][2] = max(dp[i-1][2],dp[i-1][1]+prices[i])
     * 第二次买卖的DP推到如下：
     *
     *
     * 第二次买入：从第一次卖出转换而来，或者第二次买入后保持不动
     * dp[i][3] = max(dp[i-1][3],dp[i-1][2]-prices[i])
     *
     *
     * 第二次卖出：从第二次买入转换而来，或者第二次卖出后保持不动
     * dp[i][4] = max(dp[i-1][4],dp[i-1][3]+prices[i])
     * 把上面两次买卖推导公式整合到一起就是完整的计算过程了，第一天的初始化过程请查看代码部分。
     * 最后求的利润最大值就保存在 dp[n-1][0]、dp[n-1][1]、dp[n-1][2]、dp[n-1][3]、dp[n-1][4]中，我们求出这几个值的max再返回就可以了。
     *
     * 作者：wang_ni_ma
     * 链接：https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-iii/solution/wu-chong-shi-xian-xiang-xi-tu-jie-123mai-mai-gu-pi/
     * @param prices
     * @return
     */
    public int maxProfit_3(int[] prices) {
        if (prices == null || prices.length == 0) {
            return 0;
        }
        int n = prices.length;
        //定义二维数组，5种状态
        int[][] dp = new int[n][5];
        //初始化第一天的状态
        dp[0][0]=0;
        dp[0][1]=-prices[0];
        dp[0][2]=0;
        dp[0][3]=-prices[0];
        dp[0][4]=0;
        for (int i = 1; i < n; i++) {
            //dp[i][0]相当于初始状态，它只能从初始状态转换来
            dp[i][0]=dp[i-1][0];
            //处理第一次买入、第一次卖出
            dp[i][1]=Math.max(dp[i-1][1],dp[i-1][0]-prices[i]);
            dp[i][2]=Math.max(dp[i-1][1]+prices[i],dp[i-1][2]);
            //处理第二次买入、第二次卖出
            dp[i][3]=Math.max(dp[i-1][2]-prices[i],dp[i-1][3]);
            dp[i][4]=Math.max(dp[i-1][3]+prices[i],dp[i-1][4]);
        }
        //返回最大值
        int max0 = Math.max(dp[n - 1][0], dp[n - 1][1]);
        int max1 = Math.max(dp[n - 1][2], dp[n - 1][3]);

        return Math.max(Math.max(max0,max1),dp[n-1][4]);
    }

    /**
     * 动态规划 空间优化
     * 通过二维数组的5个状态的定义，我们发现，每执行到一个状态时，只需要当前状态和前面一次状态的值就可以了。
     * 比如要计算 第一次卖出(卖出1)这个状态，就只需要买入1和卖出1这两个状态就可以了。
     *
     *
     * 计算 dp[i][x] 时(这里的x表示任意状态)，只需要两个值：
     *
     * dp[i-1][x]
     * dp[i-1][x-1] (if x>0)
     * 即求完第i天的值后，就不需要第i-1天的数据了，dp数组是不断滚动更新的，所以我们可以用5个变量来代替二维数组。
     *
     * dp0：初始化状态
     * dp1：第一次买入
     * dp2：第一次卖出
     * dp3：第二次买入
     * dp4：第二次卖出
     * 根据上面的转换关系，我们来推到一下DP公式
     * 首先是第一次买卖：
     *
     *
     * 第一次买入：从初始状态转换而来，或者第一次买入后保持不动
     * dp1 = max(dp1,dp0-prices[i])
     *
     * 第一次卖出：从第一次买入转换而来，或者第一次卖出后保持不动
     * dp2 = max(dp2,dp1+prices[i])
     * 第二次买卖的DP推到如下：
     *
     *
     * 第二次买入：从第一次卖出转换而来，或者第二次买入后保持不动
     * dp3= max(dp3,dp2-prices[i])
     *
     *
     * 第二次卖出：从第二次买入转换而来，或者第二次卖出后保持不动
     * dp4 = max(dp4,dp3+prices[i])
     * 最后求的利润最大值就保存在 d0、dp1、dp2、dp3、dp4中，我们求出这几个值的max再返回就可以了。
     *
     * 注：
     * 评论区有网友提出，正着写、倒着写都可以通过，股票系列文章中：交易k次股票 也有这样的问题。
     * 没有想明白原因，如果有朋友知道的话，麻烦在评论区留个言。
     *
     * 作者：wang_ni_ma
     * 链接：https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-iii/solution/wu-chong-shi-xian-xiang-xi-tu-jie-123mai-mai-gu-pi/
     * @param prices
     * @return
     */
    public int maxProfit_4(int[] prices) {
        if (prices == null || prices.length == 0) {
            return 0;
        }
        int n = prices.length;
        //初始化五种状态，并初始化第一天的状态
        int f0=0,f1=-prices[0],f2=0,f3=-prices[0],f4=0;
        for (int i = 1; i < n; i++) {
            //初始状态
            int newf0=f0;
            //第一次买入、卖出
            int newf1=Math.max(f1,f0-prices[i]);
            int newf2=Math.max(f2,f1+prices[i]);
            //第二次买入、卖出
            int newf3=Math.max(f3,f2-prices[i]);
            int newf4=Math.max(f4,f3+prices[i]);
            f0=newf0;
            f1=newf1;
            f2=newf2;
            f3=newf3;
            f4=newf4;
        }
        //返回最大值
        int max0 = Math.max(f0, f1);
        int max1 = Math.max(f2, f3);
        return Math.max(Math.max(max0,max1),f4);
    }
}
